#include <iostream>
#include <unordered_map>
#include <list>
#include <utility>
using namespace std;

class LRU{
public:
    LRU(int size): _size(size){}
    void put(int key, int value){
        auto it = _um.find(key);

        //如果在哈希表中找到了这个元素，更新元素并拿到头部来
        if (it != _um.end()){
            it->second->second = value;
            _nodes.splice(_nodes.begin(), _nodes, it->second);
        } else {
            //如果链表中的元素是满的
            if (_size == _nodes.size()){
                //获取要删除的元素
                auto deleteNode = _nodes.back(); 
                _nodes.pop_back();

                //unordered_map中也删除
                _um.erase(deleteNode.first);
            } 
            //在头部添加新元素
            _nodes.push_front({key, value});
            _um[key] = _nodes.begin(); 
        }
    }

    int get(int key){
        auto it = _um.find(key);
        if (it != _um.end()){
            // 更新元素
            _nodes.splice(_nodes.begin(), _nodes, it->second);

            return it->second->second;
        } else {
            return -1;
        }
    }

    void print(){
        for (auto &elem : _nodes){
            cout << "(" << elem.first
                << ", "  << elem.second
                <<   ") ";
        }
        cout << endl;
    }

private:
    int _size;
    list<pair<int, int>> _nodes;
    unordered_map<int, list<pair<int, int>>::iterator> _um;
};

void test0(){
    LRU lru(4);
    lru.put(1, 10);
    lru.put(3, 20);
    lru.put(5, 40);
    lru.put(7, 60);
    lru.print();

    lru.put(3, 90);
    lru.print();

    lru.put(10, 2);
    lru.print();
    
    cout << "get(7): " << lru.get(7) << endl; 
    cout << "get(114): " << lru.get(114) << endl; 
}

int main()
{
    test0();

    return 0;
}